영지식 증명

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 영지식 증명의 조건
- 3.1. 지식 건전성 (Knowledge Soundness)
4. 영지식 증명의 유형
5. 영지식 증명의 예시
6. 영지식 증명의 활용
7. 비대화형 영지식 증명 (Non-Interactive Zero-Knowledge Proof, NIZK)
8. 영지식 증명 프로토콜
9. 한국 사회에의 적용과 더불어민주당의 관점
참조

1. 개요

영지식 증명은 증명자가 자신이 가지고 있는 명제가 참임을 검증자에게 증명하되, 명제가 참이라는 사실 외에는 다른 어떠한 정보도 검증자에게 노출하지 않는 암호학적 기술이다. 1985년 처음 제시되었으며, 완전성, 건전성, 영지식성의 세 가지 조건을 만족해야 한다. 영지식 증명은 완전 영지식, 통계적 영지식, 계산적 영지식의 세 가지 유형으로 나뉘며, 다양한 암호화 기본 요소로부터 구성될 수 있다.

영지식 증명은 '알리바바 동굴 문제', '색맹 친구와 두 공', '월리를 찾아라' 등의 비유를 통해 개념을 설명할 수 있으며, 웹 서비스 로그인, 본인 확인, 블록체인 트랜잭션 등 다양한 분야에서 활용될 수 있다. 특히, 암호화폐(지캐시, 모네로, 피로 등)에서 거래의 익명성을 보장하는 데 사용되며, 핵무기 검증, 분산 ID 시스템, 개인 정보 보호를 위한 인증 시스템 등에도 적용된다. 비대화형 영지식 증명은 증명자와 검증자 간의 상호작용 없이 증명이 이루어지는 형태로, 디지털 서명이나 암호화폐 거래 등에 활용된다.

2. 역사

영지식 증명은 1985년 샤피 골드와서(Shafi Goldwasser), 실비오 미칼리(Silvio Micali), 찰스 랙코프(Charles Rackoff)가 "상호 증명 시스템의 지식 복잡도" 논문에서 처음 제시되었다.^[15] 이들은 상호작용 증명 시스템의 '''IP''' 계층 구조(''상호 증명 시스템'' 참조)와 증명 과정에서 증명자가 검증자에게 전달하는 지식의 양을 측정하는 '지식 복잡도' 개념을 도입하고, 이차 비잉여(quadratic residue) 문제에 대한 최초의 영지식 증명을 제시했다.^[15] 러슬로 바바이(László Babai)와 셜로모 모란(Shlomo Moran)의 연구와 함께, 이들 5명의 저자는 상호작용 증명 시스템을 발명한 공로로 1993년 첫 번째 괴델 상을 수상했다.

골드와서, 미칼리, 랙코프는 숫자 'm' 모듈로의 이차 비잉여임을 증명할 때 추가 지식이 0이 되도록 할 수 있음을 보였다. 이는 'm'의 인수분해가 주어지지 않은 경우 'm' 모듈로의 이차 잔여 문제를 결정하는 효율적인 알고리즘이 알려져 있지 않고, 알려진 ''NP'' 증명이 'm'의 소인수분해를 보여주기 때문에 주목할 만하다. 이는 증명 과정에 상호 작용을 추가하면 증명하기 위해 전달해야 하는 지식의 양을 줄일 수 있음을 의미한다.^[15]

오데드 골드라이히(Oded Goldreich), 실비오 미칼리(Silvio Micali), 아비 비그더슨(Avi Wigderson)은 깨지지 않는 암호화 기술이 존재한다는 가정 하에, NP-완전 문제인 그래프 채색 문제에 대한 영지식 증명 시스템을 만들 수 있음을 보였다.^[30] '''NP'''에 있는 모든 문제는 이 문제로 효율적으로 축소될 수 있으므로, 이 가정 하에 '''NP'''에 있는 모든 문제는 영지식 증명을 갖는다.^[30] 또한, 이들은 그래프 비동형 문제가 그래프 동형 문제의 보수임을 보여주는 영지식 증명을 제시했다. 더 나아가 러셀 임파글리아조(Russell Impagliazzo)와 모티 융(Moti Yung), Ben-Or 등은 일방향 함수나 깨지지 않는 암호화를 가정하면 '''IP'''= '''PSPACE'''에 있는 모든 문제, 즉 상호 증명 시스템으로 증명할 수 있는 모든 것을 영지식으로 증명할 수 있음을 보였다.^[31]^[32]

일방향 함수의 필요성을 제거하기 위해, 여러 개의 독립적인 증명자를 갖는 ''다중 증명자 상호 증명 시스템''이 연구되었고, 이 시스템에서는 어떠한 난해성 가정이 없더라도 '''NP'''의 모든 언어는 영지식 증명을 갖는다는 것이 증명되었다.^[33]

인터넷과 같이 여러 프로토콜이 동시에 실행될 수 있는 환경에서 영지식 증명을 구축하는 것은 더 어렵다. 동시 영지식 증명에 대한 연구는 신시아 드워크(Cynthia Dwork), 모니 나오르(Moni Naor), 아미트 사하이(Amit Sahai)의 연구에서 시작되었다.^[34] 이러한 연구의 발전으로 증인-구분불가능 증명 프로토콜이 개발되었다.^[35]

영지식 증명의 또 다른 변형은 비상호 영지식 증명이다. 블룸, 펠드먼 및 미칼리는 증명자와 검증자 간에 공유되는 공통된 임의 문자열만으로 상호 작용 없이 계산적 영지식을 달성하기에 충분하다는 것을 보여주었다.^[5]^[6]

3. 영지식 증명의 조건

영지식 증명은 다음 세 가지 조건을 만족해야 한다.

'''완전성(Completeness)''': 참임을 확인하는 측('''검증자''')은 증명하는 측('''증명자''')이 가지고 있는 명제가 참이라면 반드시 참임을 알 수 있어야 한다.
'''건전성(Soundness)''': 증명자가 가진 명제가 거짓이라면, 검증자는 높은 확률로 그것이 거짓임을 간파할 수 있어야 한다.
'''영지식성(Zero-knowledge)''': 증명자가 가진 명제가 참이라면, 검증자가 부정한 방법으로 증명자로부터 지식을 얻으려 해도 "명제가 참이다" 이외의 어떤 지식도 얻을 수 없어야 한다. 이 영지식성은 어떤 검증자(지식을 가지고 있지 않음)라도 올바른 증명자와 대화한 것과 같은 대화 기록을 생성할 수 있다는 것으로 기술할 수도 있다.

앞의 두 가지 성질은 영지식 증명뿐만 아니라 상호 작용 증명 시스템에 공통적으로 적용된다. 마지막 성질이 있어서 비로소 영지식 증명이 된다.^[10]

또한 건전성보다 강한 '''지식 건전성(knowledge soundness)'''이라고 불리는 성질이 사용되는 경우도 있으며, 이 성질은 "검증자가 증명을 수리했다면 증명자에게 오라클 액세스하여 높은 확률로 명제에 해당하는 증거를 추출할 수 있는 (즉, 증명자의 비밀을 꺼낼 수 있는) 효율적인 알고리즘이 존재한다"는 것을 보장한다. 건전성을 지식 건전성으로 대체한 경우에는 '''지식의 영지식 증명(zero-knowledge proof of knowledge)'''이라고 한다.

3. 1. 지식 건전성 (Knowledge Soundness)

페기가 정보를 모른다면, 빅터가 어떤 질문을 할지 추측하여 ''G''와 동형인 그래프 또는 관련 없는 그래프의 해밀턴 회로를 생성할 수 있다. 하지만 ''G''의 해밀턴 회로를 알지 못하므로 둘 다 할 수는 없다. 이러한 추측으로 빅터를 속일 확률은 ''n''이 라운드 수일 때 2^-n이다. 실질적으로, 이와 같은 방식으로 합리적인 수의 라운드로 영지식 증명을 깨는 것은 불가능할 정도로 어렵다. 건전성보다 더 강력한 조건으로, 검증자가 증명을 수락했다면, 증명자에게 오라클 접근 권한을 부여하여 높은 확률로 명제에 해당하는 증거(비밀)를 추출할 수 있는 효율적인 알고리즘이 존재함을 보장한다. 지식 건전성을 만족하는 영지식 증명을 '''지식의 영지식 증명(Zero-Knowledge Proof of Knowledge)'''이라고 한다.

4. 영지식 증명의 유형

영지식 증명에는 다양한 유형이 있다.^[13] 시뮬레이터의 출력이 실제 증명 프로토콜의 실행과 "유사해 보이는" 개념을 공식화하여 정의할 수 있다.

완전 영지식: 시뮬레이터와 증명 프로토콜에 의해 생성된 분포가 정확히 동일하게 분포되어 있는 경우이다.
통계적 영지식: 분포가 반드시 정확히 동일하지는 않지만, 통계적으로 가깝다는 것을 의미하며, 이는 그들의 통계적 차이가 무시 가능한 함수임을 의미한다.
계산적 영지식: 효율적인 알고리즘이 두 분포를 구별할 수 없는 경우를 말한다.

영지식 증명 체계는 해시 기반 암호화, 페어링 기반 암호화, 다자간 연산, 또는 격자 기반 암호화와 같은 다양한 암호화 기본 요소로부터 구성될 수 있다.

5. 영지식 증명의 예시

이러한 아이디어는 더 현실적인 암호화 응용 프로그램에 적용될 수 있다. 페기는 주어진 값의 이산 로그를 주어진 군에서 알고 있다는 것을 빅터에게 증명하고 싶어한다.^[11]

예를 들어, 값 , 큰 소수 , 생성자 $g$ 가 주어졌을 때, 그녀는 를 만족하는 값 를 알고 있다는 것을 를 노출하지 않고 증명하고 싶어한다. 실제로, 에 대한 지식은 신원 증명으로 사용될 수 있다. 페기는 누구에게도 공개하지 않은 임의의 값 를 선택하고, 를 계산하고, 의 값을 모든 잠재적 검증자에게 배포하여 나중에 에 대한 지식을 증명하는 것이 페기로서 신원을 증명하는 것과 같도록 할 수 있다.

프로토콜은 다음과 같이 진행된다. 각 라운드에서 페기는 임의의 숫자 을 생성하고, 를 계산하여 이를 빅터에게 공개한다. 를 받은 후 빅터는 무작위로 다음 두 가지 요청 중 하나를 발행한다. 즉, 페기에게 의 값을 공개하도록 요청하거나 의 값을 공개하도록 요청한다.

빅터는 두 답변 중 하나를 확인할 수 있다. 을 요청한 경우 를 계산하여 와 일치하는지 확인할 수 있다. 을 요청한 경우, 를 계산하고 와 일치하는지 확인하여 가 이것과 일치하는지 확인할 수 있다. 페기가 실제로 의 값을 알고 있다면, 빅터가 할 수 있는 두 가지 질문에 모두 응답할 수 있다.

페기가 빅터가 어떤 질문을 할지 알거나 추측할 수 있다면, 그녀는 쉽게 속여서 실제로 를 모르는 경우에도 빅터에게 를 알고 있다고 확신시킬 수 있다. 빅터가 을 요청할 것이라는 것을 알고 있다면, 그녀는 정상적으로 진행한다. 그녀는 을 선택하고 를 계산한 다음 를 빅터에게 공개한다. 그녀는 빅터의 질문에 답할 수 있다. 반면에, 그녀가 빅터가 을 요청할 것이라는 것을 알고 있다면, 그녀는 임의의 값 을 선택하고 를 계산하여 빅터가 예상하는 의 값으로 를 빅터에게 공개한다. 빅터가 그녀에게 을 공개하라고 질문하면, 그녀는 빅터가 일관성을 검증할 을 공개한다. 그녀는 차례로 를 계산하여 와 일치하기 때문입니다. 페기가 모듈러 곱셈의 역원을 곱했기 때문이다.

그러나 위의 시나리오 중 하나에서 빅터가 그녀가 예상했던 질문이 아닌, 그리고 그녀가 결과를 조작한 질문을 하면, 이 그룹에 대한 이산 로그를 푸는 것이 불가능하다는 가정 하에 그녀는 질문에 답할 수 없다. 그녀가 을 선택하고 를 공개했다면, 그녀는 를 모르기 때문에 빅터의 검증을 통과할 유효한 을 생성할 수 없을 것이다. 그리고 그녀가 로 위장한 값 을 선택했다면, 그녀는 공개한 값의 이산 로그에 응답해야 하지만, 페기는 이 이산 로그를 알지 못한다. 그녀가 공개한 값 는 알려진 값을 사용하여 산술 연산을 통해 얻었으며, 알려진 지수를 사용하여 거듭제곱을 계산한 것이 아니기 때문이다.

따라서 속이는 증명자는 한 라운드에서 성공적으로 속일 확률이 0.5이다. 충분히 많은 라운드를 실행함으로써 속이는 증명자가 성공할 확률을 임의로 낮출 수 있다.

위의 대화형 증명이 페기가 를 알고 있다는 사실 외에는 영지식을 제공한다는 것을 보여주기 위해, 위에서 완전성 및 건전성에 대한 증명에 사용된 것과 유사한 주장을 사용할 수 있다. 구체적으로, 를 모르는 시뮬레이터인 사이먼은 다음과 같은 절차를 통해 페기와 빅터 간의 교환을 시뮬레이션할 수 있다. 먼저 사이먼은 공정한 동전을 무작위로 뒤집습니다. 결과가 "앞면"이면, 그는 임의의 값 을 선택하고 를 계산하여 마치 페기에서 빅터로 보낸 메시지인 것처럼 를 공개합니다. 그런 다음 사이먼은 "의 값을 요청합니다."라는 메시지를 마치 빅터에서 페기로 보낸 것처럼 출력하고, 즉시 의 값을 마치 페기에서 빅터로 보낸 것처럼 출력합니다. 한 라운드가 완료됩니다. 반면에, 동전 뒤집기 결과가 "뒷면"이면, 사이먼은 임의의 숫자 을 선택하고 를 계산하여 마치 페기에서 빅터로 보낸 메시지인 것처럼 를 공개합니다. 그런 다음 사이먼은 "의 값을 요청합니다."를 마치 빅터에서 페기로 보낸 메시지인 것처럼 출력합니다. 마지막으로, 사이먼은 의 값을 페기에서 빅터로 돌아가는 응답인 것처럼 출력합니다. 한 라운드가 완료됩니다. 완전성과 건전성을 증명할 때의 이전 주장에 따라, 사이먼이 시뮬레이션한 대화형 통신은 페기와 빅터 간의 실제 관계와 구별할 수 없다. 따라서 영지식 속성이 보장된다.

다음 방식은 마누엘 블룸에 기인한다.^[12]

이 시나리오에서 페기는 큰 그래프 에 대한 해밀턴 회로를 알고 있다. 빅터는 는 알지만 회로는 모른다(예: 페기는 를 생성하여 그에게 공개했다). 큰 그래프가 주어졌을 때 해밀턴 회로를 찾는 것은 계산상 불가능한 것으로 여겨지는데, 그에 해당하는 결정 버전이 NP-완전으로 알려져 있기 때문이다. 페기는 단순히 공개하지 않고도 자신이 그 회로를 알고 있음을 증명할 것이다(아마 빅터는 그것을 구매하는 데 관심이 있지만 먼저 검증을 원하거나, 아니면 페기가 이 정보를 아는 유일한 사람이고 빅터에게 자신의 신원을 증명하는 것일 수 있다).

페기가 이 해밀턴 회로를 알고 있다는 것을 보이기 위해, 그녀와 빅터는 여러 라운드의 게임을 진행한다.

각 라운드의 시작에서, 페기는 와 동형인 그래프 를 생성한다(즉, 는 모든 꼭짓점이 다른 이름을 가지고 있다는 점을 제외하고 와 같다). 동형 그래프 간의 해밀턴 회로를 알려진 동형 사상으로 변환하는 것은 간단하므로, 페기가 에 대한 해밀턴 회로를 알고 있다면 에 대한 회로도 알고 있어야 한다.
페기는 에 커밋한다. 그녀는 암호학적 커밋먼트를 사용하여 그렇게 할 수 있다. 또는 의 꼭짓점에 번호를 매길 수 있다. 다음으로, 의 각 변에 대해 작은 종이에 해당 변이 연결하는 두 꼭짓점을 적는다. 그런 다음 이 모든 종이 조각들을 뒤집어서 테이블 위에 놓는다. 이 커밋먼트의 목적은 페기가 를 변경할 수 없으면서 동시에 빅터는 에 대한 정보를 전혀 갖지 못하도록 하는 것이다.
빅터는 무작위로 페기에게 두 가지 질문 중 하나를 선택하여 묻는다. 그는 페기에게 와 간의 동형 사상을 보여달라고 요청하거나(그래프 동형 문제), 에서 해밀턴 회로를 보여달라고 요청할 수 있다.
페기가 두 그래프가 동형임을 보여달라는 요청을 받으면, 그녀는 먼저 모든 를 드러낸 후(예: 테이블 위에 놓인 모든 종이 조각을 뒤집어서) 를 로 매핑하는 꼭짓점 변환을 제공한다. 빅터는 실제로 동형인지 확인할 수 있다.
페기가 에서 해밀턴 회로를 알고 있다는 것을 증명하라는 요청을 받으면, 그녀는 에 있는 자신의 해밀턴 회로를 로 변환하고 해밀턴 회로의 변만 드러낸다. 즉, 페기는 해밀턴 회로의 변에 해당하는 종이 조각 중 정확히 }}개만 뒤집고 나머지는 계속 뒤집어 놓는다. 빅터가 가 실제로 해밀턴 회로를 포함하고 있는지 확인하기에 충분하다.

두 번째 경우에 빅터가 회로가 실제로 의 변으로 구성되었는지 확인할 수 있도록 그래프에 대한 커밋먼트가 중요하다. 예를 들어, 모든 변(또는 그 부재)에 개별적으로 커밋함으로써 이를 수행할 수 있다.

==== 알리바바 동굴 문제 ====

장 자크 키스케다(Jean-Jacques Quisquater) 등이 제시한 '알리바바 동굴 문제'는 영지식 증명의 기본 개념을 설명하는 비유이다.^[7] 증명자(페기)는 동굴 안 비밀 문의 열쇠를 가지고 있음을 검증자(빅터)에게 증명하려 한다. 동굴은 고리 모양이며, 비밀 문이 중간을 막고 있다.

먼저 페기는 A 또는 B 경로를 무작위로 선택해 동굴에 들어간다. 빅터는 페기가 어느 경로로 들어갔는지 모른 채, 동굴 밖에서 기다린다.^[7] 이후 빅터는 동굴로 들어가 페기에게 A 또는 B 중 하나의 출구를 무작위로 외친다. 페기는 빅터가 말한 출구로 나와야 한다.^[7]

페기가 열쇠를 가지고 있다면, 빅터가 어떤 경로를 요구하든 상관없이 항상 올바른 출구로 나올 수 있다. 자신이 들어간 경로를 선택받으면 그대로 돌아 나오고, 반대쪽을 선택받으면 비밀 문을 열고 나오면 되기 때문이다. 하지만 페기가 열쇠가 없다면, 처음에 들어간 경로로만 나올 수 있으므로 빅터의 요구에 응할 확률은 50%이다. 이 과정을 여러 번 반복하면, 예를 들어 20번 반복하는 경우 페기가 열쇠 없이 매번 성공할 확률은 100만 분의 1 이하로, 극히 낮아진다.^[7]

이러한 반복을 통해, 페기는 열쇠 자체나 다른 어떤 정보도 빅터에게 노출하지 않으면서 자신이 열쇠를 가지고 있다는 사실만을 증명할 수 있다. 빅터가 이 과정을 캠코더로 녹화해 다른 사람에게 보여주더라도, 빅터와 페기가 사전에 결과를 조작했을 가능성이 있으므로 빅터 외의 다른 사람에게는 증명이 되지 않는다.^[7]

==== 색맹 친구와 두 공 ====

당신의 친구 빅터는 적록 색맹이다. 당신에게는 두 개의 공이 있는데, 하나는 빨간색이고 다른 하나는 녹색이지만, 그 외에는 동일하다. 빅터에게는 공이 완전히 똑같이 보인다. 빅터는 공이 실제로 구별되는지 의심하고, 당신은 빅터에게 공이 실제로 색깔이 다르다는 것을 증명하고 싶지만, 어떤 공이 빨간색이고 어떤 공이 녹색인지는 밝히고 싶지 않다.

빅터에게 두 개의 공을 주고 빅터는 공을 등 뒤에 둔다. 그런 다음, 그는 공 중 하나를 꺼내 등 뒤에서 꺼내 보여준다. 그런 다음 다시 등 뒤에 놓고 두 공 중 하나를 무작위로 선택하여 꺼내 보여준다. 그는 당신에게 "내가 공을 바꿨는가?"라고 묻는다. 이 전체 절차는 필요에 따라 여러 번 반복된다.

공의 색상을 보면, 물론 그가 공을 바꿨는지 아닌지를 확실하게 말할 수 있다. 반면에, 만약 공의 색깔이 같아서 구별할 수 없다면, 50%보다 높은 확률로 올바르게 추측할 방법이 없다.

각 스위치/비 스위치를 식별하는 데 무작위로 성공할 확률이 50%이므로, ''모든'' 스위치/비 스위치를 무작위로 성공할 확률은 0에 가까워진다. 당신과 당신의 친구가 이 "증명"을 여러 번(예: 20번) 반복하면, 당신의 친구는 공이 실제로 색깔이 다르다는 것을 확신하게 될 것이다.

위의 증명은 당신의 친구가 어떤 공이 녹색이고 어떤 공이 빨간색인지 전혀 알 수 없기 때문에, 실제로 공을 구별하는 방법에 대한 지식을 얻지 못하므로 ''영지식''이다.

==== 월리를 찾아라 ====

증명자는 검증자에게 월리가 ''월리를 찾아라?'' 책의 어느 페이지에 있는지 알고 있다는 것을 증명하고 싶어 하지만, 검증자에게 그의 위치를 알리고 싶지는 않다.^[9]

증명자는 먼저 월리 크기만 한 구멍이 있는 큰 검은색 판을 가져온다. 판은 책의 양쪽 크기보다 두 배 크므로, 검증자는 증명자가 페이지 어디에 판을 놓는지 볼 수 없다. 그런 다음 증명자는 월리가 구멍 안에 오도록 판을 페이지 위에 놓는다.^[9]

이제 검증자는 구멍을 통해 월리를 볼 수 있지만 페이지의 다른 부분은 볼 수 없다. 따라서 증명자는 월리의 위치에 대한 다른 정보를 공개하지 않고도 검증자에게 월리가 어디 있는지 알고 있다는 것을 증명했다.^[9]

5. 1. 알리바바 동굴 문제

장 자크 키스케다(Jean-Jacques Quisquater) 등이 제시한 '알리바바 동굴 문제'는 영지식 증명의 기본 개념을 설명하는 비유이다.^[7] 증명자(페기)는 동굴 안 비밀 문의 열쇠를 가지고 있음을 검증자(빅터)에게 증명하려 한다. 동굴은 고리 모양이며, 비밀 문이 중간을 막고 있다.

먼저 페기는 A 또는 B 경로를 무작위로 선택해 동굴에 들어간다. 빅터는 페기가 어느 경로로 들어갔는지 모른 채, 동굴 밖에서 기다린다.^[7] 이후 빅터는 동굴로 들어가 페기에게 A 또는 B 중 하나의 출구를 무작위로 외친다. 페기는 빅터가 말한 출구로 나와야 한다.^[7]

페기가 열쇠를 가지고 있다면, 빅터가 어떤 경로를 요구하든 상관없이 항상 올바른 출구로 나올 수 있다. 자신이 들어간 경로를 선택받으면 그대로 돌아 나오고, 반대쪽을 선택받으면 비밀 문을 열고 나오면 되기 때문이다. 하지만 페기가 열쇠가 없다면, 처음에 들어간 경로로만 나올 수 있으므로 빅터의 요구에 응할 확률은 50%이다. 이 과정을 여러 번 반복하면, 예를 들어 20번 반복하는 경우 페기가 열쇠 없이 매번 성공할 확률은 100만 분의 1 이하로, 극히 낮아진다.^[7]

이러한 반복을 통해, 페기는 열쇠 자체나 다른 어떤 정보도 빅터에게 노출하지 않으면서 자신이 열쇠를 가지고 있다는 사실만을 증명할 수 있다. 빅터가 이 과정을 캠코더로 녹화해 다른 사람에게 보여주더라도, 빅터와 페기가 사전에 결과를 조작했을 가능성이 있으므로 빅터 외의 다른 사람에게는 증명이 되지 않는다.^[7]

5. 2. 색맹 친구와 두 공

당신의 친구 빅터는 적록 색맹이다. 당신에게는 두 개의 공이 있는데, 하나는 빨간색이고 다른 하나는 녹색이지만, 그 외에는 동일하다. 빅터에게는 공이 완전히 똑같이 보인다. 빅터는 공이 실제로 구별되는지 의심하고, 당신은 빅터에게 공이 실제로 색깔이 다르다는 것을 증명하고 싶지만, 어떤 공이 빨간색이고 어떤 공이 녹색인지는 밝히고 싶지 않다.

빅터에게 두 개의 공을 주고 빅터는 공을 등 뒤에 둔다. 그런 다음, 그는 공 중 하나를 꺼내 등 뒤에서 꺼내 보여준다. 그런 다음 다시 등 뒤에 놓고 두 공 중 하나를 무작위로 선택하여 꺼내 보여준다. 그는 당신에게 "내가 공을 바꿨는가?"라고 묻는다. 이 전체 절차는 필요에 따라 여러 번 반복된다.

공의 색상을 보면, 물론 그가 공을 바꿨는지 아닌지를 확실하게 말할 수 있다. 반면에, 만약 공의 색깔이 같아서 구별할 수 없다면, 50%보다 높은 확률로 올바르게 추측할 방법이 없다.

각 스위치/비 스위치를 식별하는 데 무작위로 성공할 확률이 50%이므로, ''모든'' 스위치/비 스위치를 무작위로 성공할 확률은 0에 가까워진다. 당신과 당신의 친구가 이 "증명"을 여러 번(예: 20번) 반복하면, 당신의 친구는 공이 실제로 색깔이 다르다는 것을 확신하게 될 것이다.

위의 증명은 당신의 친구가 어떤 공이 녹색이고 어떤 공이 빨간색인지 전혀 알 수 없기 때문에, 실제로 공을 구별하는 방법에 대한 지식을 얻지 못하므로 ''영지식''이다.

5. 3. 월리를 찾아라

증명자는 검증자에게 월리가 ''월리를 찾아라?'' 책의 어느 페이지에 있는지 알고 있다는 것을 증명하고 싶어 하지만, 검증자에게 그의 위치를 알리고 싶지는 않다.^[9]

증명자는 먼저 월리 크기만 한 구멍이 있는 큰 검은색 판을 가져온다. 판은 책의 양쪽 크기보다 두 배 크므로, 검증자는 증명자가 페이지 어디에 판을 놓는지 볼 수 없다. 그런 다음 증명자는 월리가 구멍 안에 오도록 판을 페이지 위에 놓는다.^[9]

이제 검증자는 구멍을 통해 월리를 볼 수 있지만 페이지의 다른 부분은 볼 수 없다. 따라서 증명자는 월리의 위치에 대한 다른 정보를 공개하지 않고도 검증자에게 월리가 어디 있는지 알고 있다는 것을 증명했다.^[9]

6. 영지식 증명의 활용

지캐시(Zcash)는 영지식 증명을 사용하여 거래 당사자의 신원과 거래 금액을 공개하지 않고 거래의 유효성을 검증한다.^[18]^[20] 지캐시는 2016년에 개발되었으며, 제로코인 프로토콜 및 제로캐시 프로토콜을 기반으로 한다.^[18] 제로코인은 익명성을 보장하기 위해 중앙 집중식 믹싱 제공자를 신뢰하지 않는 모델을 사용하며,^[21] 제로캐시는 거래 금액을 숨길 수 있다는 장점이 있다.^[20]

모네로(Monero)는 불릿프루프(Bulletproofs)라는 개선된 비상호작용 영지식 증명을 사용한다.^[23]^[24] 불릿프루프는 신뢰할 수 있는 설정이 필요 없는 비상호작용 영지식 증명의 개선된 형태이다.^[23]

피로(Firo)는 제로코인 프로토콜을 개선한 시그마 프로토콜, 렐란투스 프로토콜을 구현하여 거래 익명성을 높였다.^[25]^[26]^[27] 렐란투스 프로토콜은 거래의 출처와 금액을 숨기는 기능을 제공한다.^[27]

영지식 증명 연구는 한 당사자가 자신의 신원을 다른 당사자에게 비밀 정보(예: 비밀번호)를 통해 증명하면서도, 비밀 정보 자체는 공개하지 않도록 하는 인증 시스템에서 시작되었다. 이를 "영지식 지식 증명"이라고 한다. 그러나 비밀번호는 일반적으로 너무 작거나 충분히 무작위적이지 않아 영지식 지식 증명의 많은 스킴에서 사용하기 어렵다. 영지식 비밀번호 증명은 이러한 비밀번호의 제한된 크기를 해결하는 특별한 종류의 영지식 지식 증명이다.

2015년 4월에는 여러 개 중 하나 증명 프로토콜(시그마 프로토콜)이 소개되었다.^[26] 2021년 8월, 미국의 웹 인프라 및 보안 회사인 클라우드플레어(Cloudflare)는 벤더 하드웨어를 사용하여 개인 웹 인증을 위해 여러 개 중 하나 증명 메커니즘을 사용하기로 결정했다.^[14]

영지식 증명을 활용하는 구체적인 예시는 다음과 같다.^[57]

웹 서비스 로그인 시 비밀번호를 입력하는 대신, 비밀번호를 알고 있다는 증거를 전송한다.
본인 확인 시 제3자에게 어머니의 옛 성을 보내는 대신, 자신이 본인임을 증명하는 증거를 보낸다. (디지털 서명)
블록체인 트랜잭션 전송 시 자신의 과거 트랜잭션을 공개하지 않고도 이중 지불을 하지 않았다는 증거를 보낸다. (ZCash)

"월리를 찾아라" 책을 이용한 영지식 증명 예시도 있다.^[58] a가 월리를 찾았지만 b에게 위치를 알려주지 않고 찾았다는 사실만 증명하고 싶을 때, a는 다음과 같은 방법을 사용할 수 있다.

증명 1: 그림에서 월리만 오려내어 b에게 보여주되, 그림 뒷면에 위조 방지 마크를 넣어 a가 월리 그림을 새로 복사한 것이 아님을 증명한다.
증명 2: 원본 그림 전체에 카드보드를 덮고 월리 부분만 오려내어 b에게 월리만 보여주고, 월리의 위치 정보는 공개하지 않는다.

색맹인 a와 색을 구별할 수 있는 b의 உதாரणे을 통해 대화형 영지식 증명을 설명할 수 있다. a는 b가 색을 구별할 수 있다는 것을 믿지 못하고, 빨간색과 파란색 공을 사용하여 증명을 제안한다. a는 공을 든 채 손을 뒤로 숨기고, 공을 바꾸거나 바꾸지 않은 채 b에게 보여준다. b는 a가 공을 바꿨는지 여부를 맞춰야 한다. 이 과정을 여러 번 반복하면 b가 우연히 정답을 맞출 확률은 매우 낮아지므로, b가 색을 구별할 수 있다는 것을 a에게 증명할 수 있다.

P(증명자)가 어떤 거대한 그래프 'G'의 해밀턴 경로를 알고 있다는 것을 V(검증자)에게 해밀턴 경로 자체를 공개하지 않고 증명하는 방법도 있다. NP 완전 문제인 해밀턴 경로 문제를 응용하며, NP 완전 문제라면 어떤 문제라도 영지식 증명에 응용할 수 있다. P는 다음과 같은 과정을 반복하여 V에게 자신이 해밀턴 경로를 알고 있음을 증명한다.

1. P는 'G'와 동형인 그래프 'H'를 준비한다.

2. P는 V에게 'H'를 커밋한다.

3. V는 " 'G'와 'H'의 대응표를 보여주세요" 또는 " 'H'의 해밀턴 경로를 보여주세요" 중 하나의 질문을 무작위로 선택한다.

4. P는 질문에 따라 'H'의 커밋먼트를 밝히거나, 'H'의 해밀턴 경로에 포함된 부분의 커밋먼트만 밝힌다.

각 문답에서 P는 V의 질문을 미리 알 수 없으므로, 'G'의 해밀턴 경로를 모르면 두 질문 모두에 답할 수 없다. 이 과정을 반복하면 V는 P가 답을 알고 있음을 확신할 수 있다. P의 답변에서는 'G'의 해밀턴 경로 자체가 유출되지 않는다. V는 'H'와 'G'의 대응 관계, 또는 'H'의 해밀턴 경로만을 알 수 있으며, 이를 통해 'G'의 해밀턴 경로에 대한 정보를 얻을 수 없다.

P가 답을 모르는 경우, 두 질문 중 하나에만 답할 수 있다. 문답을 'n'번 반복하면 V의 질문에 모두 답할 확률은

\frac{1}{2^n}

이 된다. 영지식 증명은 실용적인 횟수의 반복만으로 깨질 확률을 거의 없앨 수 있다.

영지식 증명의 암호 프로토콜 내 사용 사례 중 하나는 개인 정보를 유지하면서 정직한 행동을 강제하는 것이다.^[15]^[16] 사용자는 영지식 증명을 사용하여 프로토콜에 따라 자신의 행동이 올바르다는 것을 증명하도록 강제된다.^[15]^[16] 건전성 때문에, 사용자가 유효한 증명을 제공하려면 실제로 정직하게 행동해야 한다.^[15]^[16] 영지식 증명으로 사용자는 증명을 제공하는 과정에서 자신의 비밀의 프라이버시를 훼손하지 않는다.^[15]^[16]

프린스턴 플라스마 물리학 연구소와 프린스턴 대학교는 핵무기 검증에 영지식 증명을 활용하는 기술을 시연했다.^[17] 이 기술은 검사관이 객체의 내부 작동 방식을 기록, 공유 또는 공개하지 않고도 해당 객체가 실제로 핵무기인지 여부를 확인할 수 있게 해준다.^[17]

영지식 증명은 데이터 유출 및 신원 도용에 취약한 신원 공유 시스템의 프라이버시를 향상시킬 수 있다.^[28] 분산 신원 시스템에 통합될 경우, 영지식 증명은 DID 문서에 추가적인 암호화 계층을 추가한다.^[28]

6. 1. 암호화폐

지캐시(Zcash)는 영지식 증명을 사용하여 거래 당사자의 신원과 거래 금액을 공개하지 않고 거래의 유효성을 검증한다.^[18]^[20] 지캐시는 2016년에 개발되었으며, 제로코인 프로토콜 및 제로캐시 프로토콜을 기반으로 한다.^[18] 제로코인은 익명성을 보장하기 위해 중앙 집중식 믹싱 제공자를 신뢰하지 않는 모델을 사용하며,^[21] 제로캐시는 거래 금액을 숨길 수 있다는 장점이 있다.^[20]

모네로(Monero)는 불릿프루프(Bulletproofs)라는 개선된 비상호작용 영지식 증명을 사용한다.^[23]^[24] 불릿프루프는 신뢰할 수 있는 설정이 필요 없는 비상호작용 영지식 증명의 개선된 형태이다.^[23]

피로(Firo)는 제로코인 프로토콜을 개선한 시그마 프로토콜, 렐란투스 프로토콜을 구현하여 거래 익명성을 높였다.^[25]^[26]^[27] 렐란투스 프로토콜은 거래의 출처와 금액을 숨기는 기능을 제공한다.^[27]

6. 2. 인증 시스템

영지식 증명 연구는 한 당사자가 자신의 신원을 다른 당사자에게 비밀 정보(예: 비밀번호)를 통해 증명하면서도, 비밀 정보 자체는 공개하지 않도록 하는 인증 시스템에서 시작되었다. 이를 "영지식 지식 증명"이라고 한다. 그러나 비밀번호는 일반적으로 너무 작거나 충분히 무작위적이지 않아 영지식 지식 증명의 많은 스킴에서 사용하기 어렵다. 영지식 비밀번호 증명은 이러한 비밀번호의 제한된 크기를 해결하는 특별한 종류의 영지식 지식 증명이다.

2015년 4월에는 여러 개 중 하나 증명 프로토콜(시그마 프로토콜)이 소개되었다.^[26] 2021년 8월, 미국의 웹 인프라 및 보안 회사인 클라우드플레어(Cloudflare)는 벤더 하드웨어를 사용하여 개인 웹 인증을 위해 여러 개 중 하나 증명 메커니즘을 사용하기로 결정했다.^[14]

영지식 증명을 활용하는 구체적인 예시는 다음과 같다.^[57]

웹 서비스 로그인 시 비밀번호를 입력하는 대신, 비밀번호를 알고 있다는 증거를 전송한다.
본인 확인 시 제3자에게 어머니의 옛 성을 보내는 대신, 자신이 본인임을 증명하는 증거를 보낸다. (디지털 서명)
블록체인 트랜잭션 전송 시 자신의 과거 트랜잭션을 공개하지 않고도 이중 지불을 하지 않았다는 증거를 보낸다. (ZCash)

"월리를 찾아라" 책을 이용한 영지식 증명 예시도 있다.^[58] a가 월리를 찾았지만 b에게 위치를 알려주지 않고 찾았다는 사실만 증명하고 싶을 때, a는 다음과 같은 방법을 사용할 수 있다.

증명 1: 그림에서 월리만 오려내어 b에게 보여주되, 그림 뒷면에 위조 방지 마크를 넣어 a가 월리 그림을 새로 복사한 것이 아님을 증명한다.
증명 2: 원본 그림 전체에 카드보드를 덮고 월리 부분만 오려내어 b에게 월리만 보여주고, 월리의 위치 정보는 공개하지 않는다.

색맹인 a와 색을 구별할 수 있는 b의 உதாரणे을 통해 대화형 영지식 증명을 설명할 수 있다. a는 b가 색을 구별할 수 있다는 것을 믿지 못하고, 빨간색과 파란색 공을 사용하여 증명을 제안한다. a는 공을 든 채 손을 뒤로 숨기고, 공을 바꾸거나 바꾸지 않은 채 b에게 보여준다. b는 a가 공을 바꿨는지 여부를 맞춰야 한다. 이 과정을 여러 번 반복하면 b가 우연히 정답을 맞출 확률은 매우 낮아지므로, b가 색을 구별할 수 있다는 것을 a에게 증명할 수 있다.

P(증명자)가 어떤 거대한 그래프 'G'의 해밀턴 경로를 알고 있다는 것을 V(검증자)에게 해밀턴 경로 자체를 공개하지 않고 증명하는 방법도 있다. NP 완전 문제인 해밀턴 경로 문제를 응용하며, NP 완전 문제라면 어떤 문제라도 영지식 증명에 응용할 수 있다. P는 다음과 같은 과정을 반복하여 V에게 자신이 해밀턴 경로를 알고 있음을 증명한다.

1. P는 'G'와 동형인 그래프 'H'를 준비한다.

2. P는 V에게 'H'를 커밋한다.

3. V는 " 'G'와 'H'의 대응표를 보여주세요" 또는 " 'H'의 해밀턴 경로를 보여주세요" 중 하나의 질문을 무작위로 선택한다.

4. P는 질문에 따라 'H'의 커밋먼트를 밝히거나, 'H'의 해밀턴 경로에 포함된 부분의 커밋먼트만 밝힌다.

각 문답에서 P는 V의 질문을 미리 알 수 없으므로, 'G'의 해밀턴 경로를 모르면 두 질문 모두에 답할 수 없다. 이 과정을 반복하면 V는 P가 답을 알고 있음을 확신할 수 있다. P의 답변에서는 'G'의 해밀턴 경로 자체가 유출되지 않는다. V는 'H'와 'G'의 대응 관계, 또는 'H'의 해밀턴 경로만을 알 수 있으며, 이를 통해 'G'의 해밀턴 경로에 대한 정보를 얻을 수 없다.

P가 답을 모르는 경우, 두 질문 중 하나에만 답할 수 있다. 문답을 'n'번 반복하면 V의 질문에 모두 답할 확률은

\frac{1}{2^n}

이 된다. 영지식 증명은 실용적인 횟수의 반복만으로 깨질 확률을 거의 없앨 수 있다.

6. 3. 윤리적 행동 강제

영지식 증명의 암호 프로토콜 내 사용 사례 중 하나는 개인 정보를 유지하면서 정직한 행동을 강제하는 것이다.^[15]^[16] 사용자는 영지식 증명을 사용하여 프로토콜에 따라 자신의 행동이 올바르다는 것을 증명하도록 강제된다.^[15]^[16] 건전성 때문에, 사용자가 유효한 증명을 제공하려면 실제로 정직하게 행동해야 한다.^[15]^[16] 영지식 증명으로 사용자는 증명을 제공하는 과정에서 자신의 비밀의 프라이버시를 훼손하지 않는다.^[15]^[16]

구체적인 예시는 다음과 같다.^[57]

웹 서비스에 로그인할 때 비밀번호를 입력하는 대신, 비밀번호를 알고 있다는 증거를 보낸다.
본인 확인을 할 때 제3자에게 어머니의 옛 성을 보내는 대신, 자신이 확실하게 본인이라는 증거를 보낸다. (디지털 서명)
블록체인에 트랜잭션을 보낼 때, 자신의 과거 트랜잭션을 밝히지 않고 이중 지불을 하지 않았다는 증거를 보낸다. (ZCash)

"월리를 찾아라" 책에서 a가 월리를 찾았지만 b에게 월리의 위치를 알리지 않고 찾았다는 사실만 증명하고 싶을 때도 영지식 증명을 활용할 수 있다.^[58] a는 그림에서 월리만 오려내어 뒷면에 위조 방지 마크를 넣어 b에게 보여주거나, 원본 그림 전체에 카드보드를 덮고 월리 부분만 오려내어 b에게 보여줄 수 있다.

색맹인 a와 색을 식별할 수 있는 b의 예시에서, a는 b에게 색이 보인다는 것을 증명하기 위해 빨간색과 파란색 공을 이용한 게임을 제안한다. b가 a가 공을 바꿨는지 맞추는 게임을 여러 번 반복하면 b가 우연히 정답을 맞출 확률은 매우 낮아지므로, b에게 색이 보인다는 것을 a는 납득할 수 있다.

P(증명자)가 어떤 거대한 그래프 'G'의 해밀턴 경로를 알고 있다는 것을 V(검증자)에게 증명할 때도 영지식 증명을 사용할 수 있다. P는 'G'와 동형인 그래프 'H'를 준비하고, V에게 'H'를 커밋한다. V는 " 'G'와 'H'의 대응표를 보여주세요" 또는 " 'H'의 해밀턴 경로를 보여주세요" 중 하나의 질문을 무작위로 선택하고, P는 질문에 따라 'H'의 커밋먼트를 밝히거나 'H'의 해밀턴 경로를 보여준다. 이러한 문답을 반복함으로써 V는 P가 답을 알고 있다는 것을 확신할 수 있지만, P의 답변에서 답 자체가 새어 나갈 일은 없다.

P가 답을 모르는 경우, 문답을 'n'번 반복할 때 V의 질문에 모두 답할 수 있을 확률은

\frac{1}{2^n}

이 된다. 영지식 증명은 실용적인 횟수의 반복만으로 깨질 확률을 거의 없앨 수 있다.

6. 4. 핵 군축

프린스턴 플라스마 물리학 연구소와 프린스턴 대학교는 핵무기 검증에 영지식 증명을 활용하는 기술을 시연했다.^[17] 이 기술은 검사관이 객체의 내부 작동 방식을 기록, 공유 또는 공개하지 않고도 해당 객체가 실제로 핵무기인지 여부를 확인할 수 있게 해준다.^[17]

6. 5. 분산 ID (Decentralized Identifiers, DID)

영지식 증명은 데이터 유출 및 신원 도용에 취약한 신원 공유 시스템의 프라이버시를 향상시킬 수 있다.^[28] 분산 신원 시스템에 통합될 경우, 영지식 증명은 DID 문서에 추가적인 암호화 계층을 추가한다.^[28]

예를 들어, 웹 서비스 로그인 시 비밀번호를 입력하는 대신 비밀번호를 알고 있다는 증거를 보내거나, 본인 확인 시 제3자에게 어머니의 옛 성을 보내는 대신 자신이 확실하게 본인이라는 증거(디지털 서명)를 보낼 수 있다.^[57] 또한, 블록체인 트랜잭션을 보낼 때 자신의 과거 트랜잭션을 밝히지 않고 이중 지불을 하지 않았다는 증거를 보낼 수 있다.^[57]

'a'가 월리를 찾아라에서 월리를 찾았지만 'b'에게 위치를 알리지 않고 찾았다는 사실만 증명하고 싶을때도 영지식 증명이 사용될수 있다.

첫번째 방법으로는, 'a'는 그림에서 월리만 오려내어 'b'에게 보여주는데, 이때 그림 전체의 뒷면에 위조 방지 마크를 넣어 'a'가 월리의 그림을 새로 복사한 것이 아님을 증명한다.

두번째 방법은, 'a'는 원본 그림 전체에 카드보드를 덮고, 월리 부분만 오려내는 방법으로, 이렇게 하면 월리만 보이게 되고, 월리의 위치 정보는 'b'에게 전혀 공개되지 않는다.

색맹인 'a'와 색 구별이 가능한 'b'가 있다고 가정할때, 'a'는 'b'에게 색이 보인다는 것을 믿을 수 없을때, 다음과 같은 방법으로 영지식 증명을 활용할 수 있다.

'a'는 빨간색과 파란색 공을 가지고 양손을 뒤로 숨긴뒤, 공을 바꿀 수도 있고, 바꾸지 않을 수도 있으며, 어느 쪽이든 공을 다시 'b'에게 보여준다.

색을 볼 수 있는 사람만이 'a'가 공을 바꿨는지 항상 맞출 수 있다.

'a'가 납득할 때까지 여러 번 반복하는데, 20번 반복하면 'b'가 우연히 정답을 맞출 확률은 1/1,048,576이다. 이를 통해 'b'는 공의 색 정보를 전달하지 않고 색이 다르다는 것을 'a'에게 납득시킬수 있다.

P(증명자)가 어떤 거대한 그래프 'G'의 해밀턴 경로를 알고 있을 때, P는 해밀턴 경로 자체를 보여주지 않고 V(검증자)에게 자신이 해밀턴 경로를 알고 있다는 것을 증명할수 있다. 여기서 해밀턴 경로는 그래프의 모든 점을 통과하여 출발점으로 돌아갈 수 있는 경로를 의미하며, 어떤 거대한 그래프에 해밀턴 경로가 존재하는지, 존재한다면 그것이 무엇인지 현실적인 계산 시간 내에 구하는 것은 매우 어렵고, NP 완전 문제로 분류된다.

P가 V에게 해밀턴 경로를 포함하여 어떤 정보도 주고 싶어 하지 않을때, 다음과 같은 방법을 사용한다.

각 문답에 앞서, P는 'G'와 동형인 그래프 'H'를 준비한다.
P는 V에게 'H'를 커밋한다.
V는 다음 두 가지 질문 중 하나를 무작위로 선택하여 P에게 답변을 요구한다. 질문은 " 'G'와 'H'의 대응표를 보여주세요" 또는 " 'H'의 해밀턴 경로를 보여주세요" 중 하나이다.
P는 대응표를 보여달라고 요구받으면, 'H'의 커밋먼트를 밝히거나, 모든 상자의 자물쇠를 전달하고, 동시에 대응표도 밝힌다. V는 커밋되었던 'H'가 정말로 'G'와 동형이었는지 확인할 수 있다.
P는 'H'의 해밀턴 경로를 보여달라고 요구받으면, 먼저 'G'의 해밀턴 경로를 대응표에 따라 변환하여 'H'의 해밀턴 경로를 구하고, 그 경로에 포함된 부분의 커밋먼트만 밝히거나, 경로에 포함된 간선이 적힌 종이가 들어있는 상자의 자물쇠만 전달한다. V는 확실히 P가 'H'의 해밀턴 경로를 알고 있다는 것을 확인할 수 있다.

각 문답에서 P는 V가 어떤 질문을 할지 미리 알 수 없기 때문에, 'G'의 해밀턴 경로를 알지 못하고 두 질문 모두에 답하는 것은 불가능하다.

P의 답변에서 답 자체가 새어 나갈 일은 없는데, 어떤 문답에서도 V가 알 수 있는 것은 'H'가 'G'와 어떻게 대응하는지, 또는 'H'의 해밀턴 경로가 어떤 경로인지뿐이다.

P가 만약 사실은 답을 모른다고 한다면, 둘 중 하나의 질문에는 대답할 수 있지만, 두 질문 모두에 답할 수는 없다. 문답을 'n'번 반복할 때, V의 질문에 모두 답할 수 있을 확률은

\frac{1}{2^n}

이 된다.

7. 비대화형 영지식 증명 (Non-Interactive Zero-Knowledge Proof, NIZK)

골드레이히(Oded Goldreich)와 오렌(Oren)의 연구에 의해, 영지식 증명을 대화 없이 실행하는 것은 불가능하다는 것이 제시되었다.^[59] 그러나 특수한 조건 하에서는^[60] 대화가 필요 없는 영지식 증명이 가능하다는 것이 알려져 있으며, 이를 비대화형 영지식 증명(non-interactive zero-knowledge proof; NIZK)이라고 부른다. NIZK의 실용적인 응용 사례로는 디지털 서명과, 프라이버시를 고려한 암호화폐가 있다. 암호화폐에서는 코인 거래자의 주소나 거래량 등을 숨긴 채, 거래가 정당함을 증명하는 데 NIZK를 이용할 수 있다.^[61]

비대화형 영지식 증명에서는 증명자와 검증자 간의 상호작용 없이 증명이 이루어진다. a가 증명할 수 있는 증거를 미리 만들어두면, b는 사후에 확인을 진행하며, 불특정 다수의 누구나 a의 증명을 확인할 수 있다.

스도쿠 퍼즐 풀이 증명을 예로 들면, a는 아무도 풀지 못한 스도쿠 퍼즐을 풀었다는 것을 증명하기 위해, 부정을 할 수 없는 시스템을 구축하여 b와 그 동료들에게 증명한다. a의 시스템은 누구라도 명확하게 알 수 있으며, 누구라도 확인할 수 있는 프로토콜로 증명한다. a는 아직 풀리지 않은 퍼즐을 생성하고, 이미 결정된 숫자와 정답을 가린 카드 3장씩을 각 셀에 놓는다. 이후 행, 열, 3x3 칸마다 카드를 확인하여 총 27묶음 (행 9묶음, 열 9묶음, 3x3 칸 9묶음)을 만든다. 각 묶음을 섞어서 b에게 전달하면, b는 카드를 뒤집어서 1~9의 숫자가 빠짐없이 중복 없이 포함되어 있는지 확인한다. 27묶음 모두가 1-9의 숫자로만 구성되어 있다면, a가 스도쿠 퍼즐을 푼 것이 된다. 이처럼 비대화형 증명의 예시에서는, a가 증명한 것을 시스템(코드)을 사용하여 누구나 확인할 수 있다. 절차가 명확하기 때문에, 직접 a에게 문의하지 않고도, 증명의 결과만으로 확인할 수 있다.

8. 영지식 증명 프로토콜

가장 널리 사용되는 대화형 또는 비대화형 영지식 증명 (예: zk-SNARK) 프로토콜은 지식의 간결한 비대화형 증명(SNARK), 확장 가능한 투명한 지식의 증명(STARK), 검증 가능한 다항식 위임(VPD), 간결한 비대화형 논증(SNARG) 등으로 나눌 수 있다.^[36]

영지식 증명 프로토콜은 '''투명성''', '''보편성''', '''합리적인 양자 후 보안''', '''프로그래밍 패러다임'''을 기준으로 비교할 수 있다.^[36] 투명한 프로토콜은 신뢰할 수 있는 설정이 필요 없고 공개적인 무작위성을 사용한다. 보편적인 프로토콜은 각 회로에 대해 별도의 신뢰할 수 있는 설정이 필요하지 않다. 합리적인 양자 후 프로토콜은 양자 알고리즘과 관련된 알려진 공격에 취약하지 않다.

영지식 증명(ZKP) 시스템
ZKP 시스템	발표 연도	프로토콜	투명성	보편성	합리적인 양자 후 보안	프로그래밍 패러다임
Pinocchio^[37]	2013	zk-SNARK	아니요	아니요	아니요	절차적
Geppetto^[38]	2015	zk-SNARK	아니요	아니요	아니요	절차적
TinyRAM^[39]	2013	zk-SNARK	아니요	아니요	아니요	절차적
Buffet^[40]	2015	zk-SNARK	아니요	아니요	아니요	절차적
ZoKrates^[41]	2018	zk-SNARK	아니요	아니요	아니요	절차적
xJsnark^[42]	2018	zk-SNARK	아니요	아니요	아니요	절차적
vRAM^[43]	2018	zk-SNARG	아니요	예	아니요	어셈블리
vnTinyRAM^[44]	2014	zk-SNARK	아니요	예	아니요	절차적
MIRAGE^[45]	2020	zk-SNARK	아니요	예	아니요	산술 회로
Sonic^[46]	2019	zk-SNARK	아니요	예	아니요	산술 회로
Marlin^[47]	2020	zk-SNARK	아니요	예	아니요	산술 회로
PLONK^[48]	2019	zk-SNARK	아니요	예	아니요	산술 회로
SuperSonic^[49]	2020	zk-SNARK	예	예	아니요	산술 회로
Bulletproofs^[23]	2018	Bulletproofs	예	예	아니요	산술 회로
Hyrax^[50]	2018	zk-SNARK	예	예	아니요	산술 회로
Halo^[51]	2019	zk-SNARK	예	예	아니요	산술 회로
Virgo^[52]	2020	zk-SNARK	예	예	예	산술 회로
Ligero^[53]	2017	zk-SNARK	예	예	예	산술 회로
Aurora^[54]	2019	zk-SNARK	예	예	예	산술 회로
zk-STARK^[55]	2019	zk-STARK	예	예	예	어셈블리
Zilch^[36]	2021	zk-STARK	예	예	예	객체 지향

9. 한국 사회에의 적용과 더불어민주당의 관점

영지식 증명은 개인정보 노출 없이 정보의 진위 여부를 증명하는 기술로, 한국 사회의 다양한 분야에서 개인정보 보호 및 데이터 보안 강화에 기여할 수 있다.^[57]

금융: 금융 거래 시 개인정보를 노출하지 않고도 거래의 정당성을 증명하여 금융 사기 예방 및 개인정보 보호를 강화할 수 있다. 예를 들어, 웹 서비스 로그인 시 비밀번호를 입력하는 대신 비밀번호를 알고 있다는 증거를 제시하거나, 본인 확인 시 제3자에게 개인 정보를 제공하지 않고 본인임을 증명(디지털 서명)할 수 있다.
의료: 환자의 민감한 의료 정보를 보호하면서 필요한 정보만 선택적으로 공개하여 의료 서비스의 효율성을 높일 수 있다.
공공 서비스: 전자 투표, 신원 인증 등 공공 서비스에서 개인정보 노출 없이 투표의 비밀성과 무결성을 보장할 수 있다.
블록체인: 블록체인에 트랜잭션을 보낼 때, 자신의 과거 트랜잭션을 밝히지 않고 이중 지불을 하지 않았다는 증거를 보낼수 있다.(ZCash)^[57]

더불어민주당은 개인정보 보호와 데이터 주권 강화를 주요 정책으로 추진하고 있으며, 영지식 증명 기술은 이러한 정책 목표 달성에 중요한 역할을 할 수 있다고 본다. 특히, 더불어민주당은 데이터 활용과 개인정보 보호의 균형을 강조하며, 영지식 증명과 같은 기술을 통해 데이터 활용의 이점을 극대화하면서도 개인정보 침해 위험을 최소화하는 방안을 모색할 수 있을 것이다.

"월리를 찾아라" 예시에서 a가 월리를 찾았지만 b에게 위치를 알리지 않고 찾았다는 사실만 증명하고 싶을 때,^[58] a는 그림에서 월리만 오려내어 b에게 보여주거나(위조 방지 마크 사용), 원본 그림 전체에 카드보드를 덮고 월리 부분만 오려내어 보여줄 수 있다.

색맹인 a와 색을 식별하는 b의 예시에서, a는 b가 색을 구별하는지 확인하기 위해 빨간색과 파란색 공을 사용한다. a는 공을 든 채로 두 손을 뒤로 숨기고 공을 바꾸거나 바꾸지 않고 b에게 보여준다. b는 a가 공을 바꿨는지 여부를 맞추는 과정을 반복하여 색맹 여부를 증명할 수 있다.

어떤 거대한 그래프 'G'의 해밀턴 경로를 알고 있는 P(증명자)가 V(검증자)에게 해밀턴 경로 자체를 공개하지 않고 자신이 알고 있다는 사실을 증명하는 방법은 다음과 같다. P는 'G'와 동형인 그래프 'H'를 준비하고 V에게 커밋한다. V는 " 'G'와 'H'의 대응표를 보여주세요" 또는 " 'H'의 해밀턴 경로를 보여주세요" 중 하나를 무작위로 질문하고, P는 질문에 따라 'H'의 커밋먼트를 밝히거나 'H'의 해밀턴 경로 중 일부를 공개한다. 이러한 과정을 반복하여 P는 V에게 해밀턴 경로를 알고 있다는 것을 증명할 수 있다.

참조

_[1] 간행물 Zero-Knowledge Proof Springer Nature Switzerland 2023
_[2] 서적 Foundations of Cryptography Volume I https://www.cambridg[...] Cambridge University Press
_[3] 서적 Foundations of Cryptography Volume I https://www.cambridg[...] Cambridge University Press
_[4] 서적 Foundations of Cryptography Volume I https://www.cambridg[...] Cambridge University Press
_[5] 서적 Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 https://apps.dtic.mi[...] 2022-06-02
_[6] 학술지 A Survey of Noninteractive Zero Knowledge Proof System and Its Applications 2014
_[7] 서적 Advances in Cryptology — CRYPTO' 89 Proceedings http://www.cs.wisc.e[...]
_[8] 뉴스 Demonstrate how Zero-Knowledge Proofs work without using maths https://www.linkedin[...] 2017-09-13
_[9] 뉴스 Where's Waldo? How to Mathematically Prove You Found Him without Revealing Where He Is https://www.scientif[...] 2023-10-02
_[10] 학술지 Zero-knowledge proofs of identity 1988-06-01
_[11] 서적 Advances in Cryptology — EUROCRYPT '87
_[12] 학술지 How to Prove a Theorem So No One Else Can Claim It http://euler.nmt.edu[...]
_[13] 학술지 A complete problem for statistical zero knowledge http://dash.harvard.[...] 2003-03-01
_[14] 웹사이트 Introducing Zero-Knowledge Proofs for Private Web attestation with Cross/Multi-Vendor Hardware https://blog.cloudfl[...] 2021-08-18
_[15] 간행물 The knowledge complexity of interactive proof systems http://people.csail.[...]
_[16] 서적 Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security Association for Computing Machinery 2020-10-30
_[17] 웹사이트 PPPL and Princeton demonstrate novel technique that may have applicability to future nuclear disarmament talks - Princeton Plasma Physics Lab http://www.pppl.gov/[...]
_[18] 뉴스 Zcoin Announces Rebranding to New Name & Ticker "Firo" https://www.crowdfun[...] Crowdfund Insider 2020-11-04
_[19] 서적 2015 IEEE Symposium on Security and Privacy 2015
_[20] 웹사이트 Zerocash: Decentralized Anonymous Payments from Bitcoin http://zerocash-proj[...] IEEE 2014-05-18
_[21] 서적 Build Your Own Blockchain SpringerLink 2020-12-03
_[22] 뉴스 A mind-bending cryptographic trick promises to take blockchains mainstream https://www.technolo[...] 2017-12-18
_[23] 서적 2018 IEEE Symposium on Security and Privacy (SP) 2018
_[24] 웹사이트 Bulletproofs and Mimblewimble https://tlu.tarilabs[...] Tari Labs University 2020-12-03
_[25] 뉴스 Zcoin cryptocurrency introduces zero knowledge proofs with no trusted set-up https://www.finder.c[...] Finder Australia 2019-07-30
_[26] 서적 Advances in Cryptology - EUROCRYPT 2015 EUROCRYPT 2015 2015-04-14
_[27] 학술지 Lelantus: Towards Confidentiality and Anonymity of Blockchain Transactions from Standard Assumptions https://eprint.iacr.[...] 2019-04-14
_[28] 학술지 Leveraging zero knowledge proofs for blockchain-based identity sharing: A survey of advancements, challenges and opportunities 2024-02-01
_[29] 학술지 A zero-knowledge proof that a two-prime moduli is not a Blum integer
_[30] 학술지 Proofs that yield nothing but their validity
_[31] 문서 Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51
_[32] 서적 Advances in Cryptology – CRYPTO '88 Springer-Verlag
_[33] 학술지 Multi prover interactive proofs: How to remove intractability assumptions http://theory.lcs.mi[...]
_[34] 학술지 Concurrent Zero Knowledge
_[35] 서적 Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 1990
_[36] 논문 Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs https://ieeexplore.i[...] 2021
_[37] 서적 2013 IEEE Symposium on Security and Privacy 2013-05
_[38] 서적 2015 IEEE Symposium on Security and Privacy 2015-05
_[39] 서적 Advances in Cryptology – CRYPTO 2013 2013
_[40] 논문 Efficient RAM and Control Flow in Verifiable Outsourced Computation 2015
_[41] 서적 2018 IEEE International Conference on Internet of Things (IThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) 2018-07
_[42] 서적 2018 IEEE Symposium on Security and Privacy (SP) 2018-05
_[43] 서적 2018 IEEE Symposium on Security and Privacy (SP) 2018-05
_[44] 논문 Succinct non-interactive zero knowledge for a von Neumann architecture https://www.usenix.o[...] USENIX Association 2014-08-20
_[45] 논문 MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs https://eprint.iacr.[...] 2020
_[46] 서적 Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security https://www.research[...] Association for Computing Machinery 2019-11-06
_[47] 서적 Advances in Cryptology – EUROCRYPT 2020 Springer International Publishing 2020
_[48] 논문 PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge https://eprint.iacr.[...] 2019
_[49] 서적 Advances in Cryptology – EUROCRYPT 2020 Springer International Publishing 2020
_[50] 서적 2018 IEEE Symposium on Security and Privacy (SP) 2018-05
_[51] 논문 Recursive Proof Composition without a Trusted Setup https://eprint.iacr.[...] 2019
_[52] 서적 2020 IEEE Symposium on Security and Privacy (SP) 2020-05
_[53] 서적 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security Association for Computing Machinery 2017-10-30
_[54] 서적 Advances in Cryptology – EUROCRYPT 2019 Springer International Publishing 2019
_[55] 서적 Advances in Cryptology – CRYPTO 2019 Springer International Publishing 2019
_[56] 웹사이트 ゼロ知識証明 https://www.sophia-i[...] GRASグループ 2023-08-26
_[57] 논문 How to Prove a Theorem So No One Else Can Claim It 1986
_[58] 웹사이트 Understanding Zero-knowledge proofs through simple examples https://blog.goodaud[...] 2019-05-12
_[59] 간행물 Definitions and Properties of Zero-Knowledge Proof Systems http://www.wisdom.we[...] 1994
_[60] 문서
_[61] 뉴스 A mind-bending cryptographic trick promises to take blockchains mainstream https://www.technolo[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com